This invention relates to image processing and more particularly to a method and apparatus for image segmentation which is the operation of dividing an image into regions represented by the image data.
Many different image processing applications detect objects and images by segmenting the image into regions represented in the image data and then identifying the regions that belong to the object while discarding the regions that belong to the background. Examples of such applications are optical character recognition, military target recognition, and assembly line product inspection. In optical character recognition applications, for example, the various characters have to be segmented before they can be identified. The text entitled xe2x80x9cFundamentals of Digital Image Processingxe2x80x9d by A. J. Jain, published by Prentice-Hall, Englewood Cliffs, N.J., in 1989, describes many prior art techniques of image segmentation. These prior art techniques attempt to identify the edges or boundaries of the regions to be segmented by methods, such as edge detection, texture analysis, and contour following. The prior art techniques typically fail to satisfactorily achieve segmentation because the edges or boundaries are almost always noisy and incomplete. Yet the boundaries must somehow be joined or completed in order to separate the regions so they can be properly identified. One class of techniques for segmentation are called connectivity techniques which trace the edges and attempt to connect them. The incomplete edges are attempted to be linked by heuristic graph searching or by dynamic programming to optimize some evaluation function. The well-known Hough transform, described in the aforementioned Jain text, is employed to identify straight or curved lines in incomplete edges. Other techniques include template matching, region growing and morphological processes.
None of the prior art methods for boundary completion or image segmentation are satisfactory. For example, the Hough transform fails in noisier shadow corrupted parts of the image where the boundaries do not have clearly linear structure. Contour following methods also fail under these conditions. Texture analysis is useless where the image does not have meaningful textural information. Template matching cannot be used in absence of advance knowledge of the anticipated shapes of the regions. None of the prior art techniques will work to achieve segmentation on some images.
Accordingly, there is a need for an image segmentation technique which will be effective to segment images containing shadow corrupted parts of the image or have boundaries which do not have clear linear structure and where the images lack meaningful textural information.
In accordance with the invention, an image is segmented by first identifying and labeling the pixels containing image boundaries. The image boundaries are fattened by adding pixels to the boundaries to separate the region of the image which are not labeled as boundaries into separate segments. The separate segments are then grown back to their original size before the boundaries were fattened. This operation has the effect of linking the boundaries together to separate the image into segments. Since the system completes boundaries between the segments formed by the system, the system may also be considered as a boundary completion or edge linking system. The technique is effective in segmenting images in which the boundaries in the image are incomplete and which could not be segmented by prior art techniques.